// 题意：给定a, b, d问多少整数对(x, y)满足x<=a, y<=b且gcd(x, y) = d。有
//       n(<=50000)组询问。
//
// 题解：首先，考虑要使gcd(x, y) = d, 那么x=k1*d, y=k2*d, 且gcd(k1, k2) = 1。
//       原题就转化成了有多少数对(x', y')满足x'<=floor(a/d), y'<=floor(b/d)，
//       且gcd(x', y')=1的对数。
//       这是一类问题，
//       假设f(i)为x<=n, y<=m且gcd(x, y)=i的对数，
//           F(i)为x<=n, y<=m且i | gcd(x, y)的对数。
//       很容易知道F(i)=floor(n/i)*floor(m/i)，
//       且用第二种形式的莫比乌斯反演就可以知道
//       f(i) = sigma(μ(d/i)*F(d)) where i|d
//            = sigma(μ(d/i)*floor(n/d)*floor(m/d)) where i|d
//       然后如果可以O(min(n, m))做，枚举这个倍数d然后算出f(i)，
//       不过还是要超时。
//       注意到floor(n/d)以及floor(m/d)都是一块一块相等的，并且大概是O(sqrt(n))
//       的级别，所以可以按块来枚举d，然后维护莫比乌斯的前缀和就好。
//       详细写法见程序，非常简短。
//
// 统计：6328ms, 20min, 1a
// run: $exec < input
#include <cstdio>
#include <algorithm>

int const maxn = 50100;
bool not_prime[maxn];
int prime[maxn];
int mo[maxn];
int sum[maxn];
int tot;

void init_mobius(int n = maxn)
{
	mo[1] = 1;
	for (int i = 2; i < n; i++) {
		if (!not_prime[i]) mo[i] = -1, prime[++tot] = i;
		for (int j = 1; prime[j] * i < n; j++) {
			not_prime[prime[j] * i] = true;
			if (i % prime[j] == 0) {
				mo[prime[j] * i] = 0;
				break;
			}
			mo[prime[j] * i] = -mo[i];
		}
	}
	sum[1] = mo[1];
	for (int i = 2; i < n; i++) sum[i] = sum[i - 1] + mo[i];
}

int inverse(int n, int m)
{
	int ans = 0, pos = 1;
	for (int i = pos; i <= n; i = pos + 1) {
		pos = std::min(n / (n/i), m / (m/i));
		ans += (sum[pos] - sum[i - 1]) * (n/i) * (m/i);
	}
	return ans;
}

int main()
{
	init_mobius();
	int T; std::scanf("%d", &T);
	while (T--) {
		int a, b, c;
		std::scanf("%d %d %d", &a, &b, &c);
		int n = a / c, m = b / c;
		if (n > m) std::swap(n, m);
		std::printf("%d\n", inverse(n, m));
	}
}

